package ai.zixing.mashibing.basic_class.class11;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 打印一个字符串的全部子序列
 * 【字符串先后顺序不变】
 */
public class Code02_PrintAllSubsquences {

    public static List<String> subs(String s) {
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str, 0, ans, path);
        return ans;
    }

    // str 固定不变
    // index 此时下标位置：要，还是不要
    // ans 如果 index 到终止为止，收集沿途的答案
    // path 沿途路径，之前做出的选择
    // 深度优先遍历
    public static void process1(char[] str, int index, List<String> ans, String path) {
        if (index == str.length) {
            ans.add(path);
            return;
        }
        String no = path;
        // 不要当前字符
        process1(str, index + 1, ans, no);
        // 要当前字符
        String yes = path + str[index];
        process1(str, index + 1, ans, yes);
    }


    // 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
    public static List<String> subsNoRepeat(String s) {
        char[] str = s.toCharArray();
        String path = "";
        HashSet<String> set = new HashSet<>();
        process2(str, 0, set, path);
        List<String> ans = new ArrayList<>();
        for (String cur : set) {
            ans.add(cur);
        }
        return ans;
    }

    public static void process2(char[] str, int index, HashSet<String> ans, String path) {
        if (index == str.length) {
            ans.add(path);
            return;
        }
        String no = path;
        process2(str, index + 1, ans, no);
        String yes = path + str[index];
        process2(str, index + 1, ans, yes);
    }

    public static void main(String[] args) {
        String test = "aacc";
        List<String> ans1 = subs(test);
        List<String> ans2 = subsNoRepeat(test);
        for (String str : ans1) {
            System.out.println(str);
        }
        System.out.println("===============");
        for (String str : ans2) {
            System.out.println(str);
        }
        System.out.println("==============");
    }
}

